{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pancake Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pancakeSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #煎饼排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> ，请使用 <strong>煎饼翻转</strong><em> </em>完成对数组的排序。</p>\n",
    "\n",
    "<p>一次煎饼翻转的执行过程如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择一个整数 <code>k</code> ，<code>1 <= k <= arr.length</code></li>\n",
    "\t<li>反转子数组 <code>arr[0...k-1]</code>（<strong>下标从 0 开始</strong>）</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，<code>arr = [3,2,1,4]</code> ，选择 <code>k = 3</code> 进行一次煎饼翻转，反转子数组 <code>[3,2,1]</code> ，得到 <code>arr = [<strong>1</strong>,<strong>2</strong>,<strong>3</strong>,4]</code> 。</p>\n",
    "\n",
    "<p>以数组形式返回能使 <code>arr</code> 有序的煎饼翻转操作所对应的 <code>k</code> 值序列。任何将数组排序且翻转次数在 <code>10 * arr.length</code> 范围内的有效答案都将被判断为正确。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[3,2,4,1]\n",
    "<strong>输出：</strong>[4,2,4,3]\n",
    "<strong>解释：</strong>\n",
    "我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。\n",
    "初始状态 arr = [3, 2, 4, 1]\n",
    "第一次翻转后（k = 4）：arr = [<strong>1</strong>, <strong>4</strong>, <strong>2</strong>, <strong>3</strong>]\n",
    "第二次翻转后（k = 2）：arr = [<strong>4</strong>, <strong>1</strong>, 2, 3]\n",
    "第三次翻转后（k = 4）：arr = [<strong>3</strong>, <strong>2</strong>, <strong>1</strong>, <strong>4</strong>]\n",
    "第四次翻转后（k = 3）：arr = [<strong>1</strong>, <strong>2</strong>, <strong>3</strong>, 4]，此时已完成排序。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1,2,3]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：\n",
    "</strong>输入已经排序，因此不需要翻转任何内容。\n",
    "请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= arr.length <= 100</code></li>\n",
    "\t<li><code>1 <= arr[i] <= arr.length</code></li>\n",
    "\t<li><code>arr</code> 中的所有整数互不相同（即，<code>arr</code> 是从 <code>1</code> 到 <code>arr.length</code> 整数的一个排列）</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pancake-sorting](https://leetcode.cn/problems/pancake-sorting/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pancake-sorting](https://leetcode.cn/problems/pancake-sorting/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,1]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    stack = []\n",
    "\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        lenth = len(arr)\n",
    "        if lenth <= 1:\n",
    "            return arr\n",
    "\n",
    "        def fliplist(listtmp, k):\n",
    "            self.stack.append(k)\n",
    "            lenth = k\n",
    "            for i in range(lenth // 2):\n",
    "                tmp = listtmp[lenth - 1 - i]\n",
    "                listtmp[lenth - 1 - i] = listtmp[i]\n",
    "                listtmp[i] = tmp\n",
    "            return listtmp\n",
    "\n",
    "        self.stack = []\n",
    "        arrtmp = sorted(arr)\n",
    "        while arrtmp:\n",
    "            index = arr.index(arrtmp.pop())\n",
    "            if index > 0:\n",
    "                fliplist(arr, index + 1)\n",
    "            fliplist(arr, len(arrtmp)+1)\n",
    "        return self.stack\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = []\n",
    "\n",
    "        while n > 1:\n",
    "            for i in range(n):\n",
    "                if arr[i] == n:\n",
    "                    if i != 0:\n",
    "                        ans.append(i + 1)\n",
    "                    ans.append(n)\n",
    "                    n -= 1\n",
    "                    arr = arr[-1:i:-1] + arr[0:i]\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = []\n",
    "        last = n \n",
    "        \n",
    "        while last > 0:\n",
    "            idx = arr.index(last)\n",
    "            if idx == last - 1:  # 如果 last 已经在排序后的位置则不用额外操作\n",
    "                last -= 1 \n",
    "                continue \n",
    "                \n",
    "            ans.append(idx + 1)\n",
    "            ans.append(last)\n",
    "            \n",
    "            for i in range((idx + 1) // 2):\n",
    "                arr[i], arr[idx-i] = arr[idx-i], arr[i]\n",
    "             \n",
    "            for i in range(last // 2):\n",
    "                arr[i], arr[last - 1 - i] = arr[last - 1 - i], arr[i]\n",
    "                \n",
    "            last -= 1 \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        def find_max_index(array_input):\n",
    "            index = 0\n",
    "            for i in range(1, len(array_input)):\n",
    "                if array_input[i] > array_input[index]:\n",
    "                    index = i\n",
    "            return index + 1\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(arr), 0, -1):\n",
    "            max_index = find_max_index(arr[:i])\n",
    "            arr = arr[:max_index][::-1] + arr[max_index:]\n",
    "            arr = arr[:i][::-1] + arr[i:]\n",
    "            res += [max_index, i]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n, 1, -1):\n",
    "            p = max(arr[:i])\n",
    "            idx = arr[:i].index(p)\n",
    "            if idx == i:\n",
    "                continue\n",
    "            \n",
    "            arr[:idx + 1] = arr[:idx + 1][::-1]\n",
    "            arr[:i] = arr[:i][::-1]\n",
    "            ans.append(idx + 1)\n",
    "            ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        results = []\n",
    "        n = len(arr)\n",
    "        \n",
    "        def reverse(arr, end):\n",
    "            start = 0\n",
    "            while start < end:\n",
    "                arr[start], arr[end] = arr[end], arr[start]\n",
    "                start += 1\n",
    "                end -= 1\n",
    "\n",
    "        for i in range(n-1, 0, -1):\n",
    "            max_index = arr.index(i+1)\n",
    "            if max_index != i:\n",
    "                if max_index != 0:\n",
    "                    results.append(max_index + 1)\n",
    "                    reverse(arr, max_index)\n",
    "                results.append(i + 1)\n",
    "                reverse(arr, i)\n",
    "        \n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        j = len(arr)\n",
    "        a = []\n",
    "        t = 0\n",
    "        while j >= 1:\n",
    "            maxs = max(arr[0:j])\n",
    "            m = arr.index(maxs)\n",
    "            if m == 0:\n",
    "                t+=1\n",
    "                arr[0:j] = arr[j-1:-1:-1]\n",
    "                a.append(j)\n",
    "            if m > 0 and m < j-1 :\n",
    "                t+=1\n",
    "                arr[0:m+1] = arr[m:-1:-1]\n",
    "                a.append(m+1)\n",
    "                arr[0:j] = arr[j-1:-1:-1]\n",
    "                a.append(j)\n",
    "            j-=1\n",
    "        if t <= 10*len(arr):\n",
    "            return a'''\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            x = arr.index(len(arr))\n",
    "            res.append(x+1)\n",
    "            res.append(len(arr))\n",
    "            arr = (arr[:x+1][::-1]+arr[x+1:])[::-1][:-1]\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for num in range(1,len(arr)+1)[::-1]:\n",
    "            idx = arr.index(num)\n",
    "\n",
    "            if idx+1 != num:\n",
    "                if arr[0] != num:\n",
    "                    ans.append(idx + 1)\n",
    "                    arr[:idx + 1] = arr[:idx + 1][::-1]\n",
    "                ans.append(num)\n",
    "                arr[:num] = arr[:num][::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "#         ans = []\n",
    "#         for n in range(len(arr), 1, -1):\n",
    "#             index = 0\n",
    "#             for i in range(n):\n",
    "#                 if arr[i] > arr[index]:\n",
    "#                     index = i\n",
    "#             if index == n - 1:\n",
    "#                 continue\n",
    "#             m = index\n",
    "#             for i in range((m + 1) // 2):\n",
    "#                 arr[i], arr[m - i] = arr[m - i], arr[i]  # 原地反转\n",
    "#             for i in range(n // 2):\n",
    "#                 arr[i], arr[n - 1 - i] = arr[n - 1 - i], arr[i]  # 原地反转\n",
    "#             ans.append(index + 1)\n",
    "#             ans.append(n)\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = []\n",
    "        while n:\n",
    "            i = arr.index(n)\n",
    "            res.append(i + 1)\n",
    "            arr = arr[: i + 1][::-1] + arr[i + 1 :]\n",
    "            # print(i)\n",
    "            res.append(n)\n",
    "            arr = arr[:n][::-1] + arr[n:]\n",
    "            # print(arr)\n",
    "            n -= 1\n",
    "        return res\n",
    "\n",
    "\n",
    "#         res = []\n",
    "#         n = len(arr)\n",
    "#         while n:\n",
    "#             idx = arr.index(n)\n",
    "#             if idx == n - 1:\n",
    "#                 n -= 1\n",
    "#                 continue\n",
    "#             res.append(idx + 1)\n",
    "#             A = arr[: idx + 1][::-1] + arr[idx + 1 :]\n",
    "#             res.append(n)\n",
    "#             A = A[:n][::-1] + A[n:]\n",
    "#             n -= 1\n",
    "#         # print(A)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        index = len(arr)\n",
    "        while index > 0:\n",
    "            if arr[index-1] == index:\n",
    "                index -= 1\n",
    "                continue\n",
    "            \n",
    "            i = index - 2\n",
    "            while i >= 0:\n",
    "                if arr[i] == index: break\n",
    "                i -= 1\n",
    "\n",
    "            ans.extend([i+1, index])\n",
    "            arr[:index-1] = arr[index-1:i:-1] + arr[:i]\n",
    "            arr[index-1] = index\n",
    "            index -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, cakes: List[int]) -> List[int]:\n",
    "        # 记录反转操作序列\n",
    "        self.res = []\n",
    "        self.sort(cakes, len(cakes))\n",
    "        return self.res\n",
    "    \n",
    "    def sort(self, cakes: List[int], n: int) -> None:\n",
    "        # base case\n",
    "        if n == 1:\n",
    "            return\n",
    "        # 寻找最大饼的索引\n",
    "        max_cake = 0\n",
    "        max_cake_index = 0\n",
    "        for i in range(n):\n",
    "            if cakes[i] > max_cake:\n",
    "                max_cake_index = i\n",
    "                max_cake = cakes[i]\n",
    "        # 第一次翻转，将最大饼翻到最上面\n",
    "        self.reverse(cakes, 0, max_cake_index)\n",
    "        self.res.append(max_cake_index + 1)\n",
    "        # 第二次翻转，将最大饼翻到最下面\n",
    "        self.reverse(cakes, 0, n - 1)\n",
    "        self.res.append(n)\n",
    "\n",
    "        # 递归调用\n",
    "        self.sort(cakes, n - 1)\n",
    "        \n",
    "    def reverse(self, arr: List[int], i: int, j: int) -> None:\n",
    "        while i < j:\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "            i += 1\n",
    "            j -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n=len(arr)\n",
    "        res=[]\n",
    "        sn=n\n",
    "        dc={}\n",
    "        \n",
    "        def switchpan(arr,s):\n",
    "            li,ri=0,s-1\n",
    "            while ri>li:\n",
    "                dc[arr[li]]=ri+1\n",
    "                dc[arr[ri]]=li+1\n",
    "                arr[li],arr[ri]=arr[ri],arr[li]\n",
    "                li+=1\n",
    "                ri-=1\n",
    "\n",
    "                \n",
    "        for i in range(n):\n",
    "            dc[arr[i]]=i+1\n",
    "            \n",
    "        while sn>0:\n",
    "            if sn!=dc[sn]:\n",
    "                if dc[sn]>1:\n",
    "                    res.append(dc[sn])\n",
    "                    switchpan(arr,dc[sn])\n",
    "                res.append(sn)\n",
    "                switchpan(arr,sn)\n",
    "##            print(sn,dc,arr,res)\n",
    "                \n",
    "            sn-=1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        for n in range(len(arr)-1,0,-1):\n",
    "            j=n\n",
    "            for i in range(n+1):\n",
    "                if arr[i]>arr[j]:\n",
    "                    j=i\n",
    "            if j==n: continue\n",
    "            for i in range((j+1)//2):\n",
    "                arr[i],arr[j-i]=arr[j-i],arr[i]       #原地排序技巧\n",
    "            for i in range((n+1)//2):\n",
    "                arr[i],arr[n-i]=arr[n-i],arr[i]       #原地排序技巧\n",
    "            ans.append(j+1)\n",
    "            ans.append(n+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        arrlen = len(arr)\n",
    "        cnt = arrlen\n",
    "        while cnt > 0:\n",
    "            if arr[cnt-1] != cnt:\n",
    "                pos = 0\n",
    "                for i in range(cnt):\n",
    "                    if arr[i] == cnt:\n",
    "                        pos = i\n",
    "                        break\n",
    "                arr[:pos+1] = reversed(arr[:pos+1])\n",
    "                ans.append(pos+1)\n",
    "                arr[:cnt] = reversed(arr[:cnt])\n",
    "                ans.append(cnt)\n",
    "            cnt -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = []\n",
    "        for k in range(n, 1, -1):\n",
    "            idx = arr.index(k)\n",
    "            if idx != k - 1:\n",
    "                arr[:idx + 1] = arr[:idx + 1][::-1]\n",
    "                ans.append(idx + 1)\n",
    "                arr[:k] = arr[:k][::-1]\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        nums = []\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            nums.append([arr[i],i])\n",
    "        for i in range(len(arr)):\n",
    "            max_num = 0\n",
    "            pos = -1\n",
    "            for j in range(len(arr)-i):\n",
    "                if max_num<arr[j]:\n",
    "                    max_num = arr[j]\n",
    "                    pos = j\n",
    "            if pos!=len(arr)-i-1:\n",
    "                \n",
    "                res.append(pos+1)\n",
    "                arr[:pos+1] = reversed(arr[:pos+1])\n",
    "                res.append(len(arr)-i)\n",
    "                arr[:len(arr)-i] = reversed(arr[:len(arr)-i])\n",
    "                # print(arr)\n",
    "        return res   \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "    #     def reverse(left, right):\n",
    "    #         while left < right:\n",
    "    #             arr[left], arr[right] = arr[right], arr[left]\n",
    "    #             left += 1\n",
    "    #             right -= 1\n",
    "    #     if len(arr) == 1:\n",
    "    #         return []\n",
    "    #     ans = []\n",
    "    #     for n in range(len(arr)-1, 1, -1):\n",
    "    #         index = 0\n",
    "    #         for i in range(n + 1):\n",
    "    #             if arr[i] > arr[index]:\n",
    "    #                 index = i\n",
    "    #         if index == n:\n",
    "    #             continue\n",
    "    #         # if index > 0:\n",
    "    #         reverse(0, index)\n",
    "    #         ans.append(index + 1)\n",
    "    #         reverse(0, n)\n",
    "    #         ans.append(n+1)\n",
    "    #     return ans\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for n in range(len(arr), 1, -1):\n",
    "            index = 0\n",
    "            for i in range(n):\n",
    "                if arr[i] > arr[index]:\n",
    "                    index = i\n",
    "            if index == n - 1:\n",
    "                continue\n",
    "            m = index\n",
    "            for i in range((m + 1) // 2):\n",
    "                arr[i], arr[m - i] = arr[m - i], arr[i]  # 原地反转\n",
    "            for i in range(n // 2):\n",
    "                arr[i], arr[n - 1 - i] = arr[n - 1 - i], arr[i]  # 原地反转\n",
    "            ans.append(index + 1)\n",
    "            ans.append(n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = []\n",
    "        t = 0\n",
    "        length = n\n",
    "        while n!=0 and t<5:\n",
    "            #t +=1\n",
    "            for i in range(length):\n",
    "                if arr[i]==n:\n",
    "                    ans.append(i+1)\n",
    "                    #print(arr)\n",
    "                    arr = arr[i::-1]+arr[i+1:]\n",
    "                    ans.append(n)\n",
    "                    arr = arr[n-1::-1]\n",
    "                    n -= 1\n",
    "                    #print(arr,n)\n",
    "                    break\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pancakeSort(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        N = len(A)\n",
    "        res = []\n",
    "        for x in range(N, 0, -1):\n",
    "            i = A.index(x)\n",
    "            res.extend([i + 1, x])\n",
    "            A = A[:i:-1] + A[:i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            idx = max(enumerate(arr[:n-i]), key = lambda x: x[1])[0]\n",
    "            res.append(idx+1)\n",
    "            arr[:idx + 1] = arr[idx+1::-1]\n",
    "            res.append(n-i)\n",
    "            arr[:n-i] = arr[n-i::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            max_num = max(arr)\n",
    "            idx = arr.index(max_num)\n",
    "            k = idx+1\n",
    "            res.append(k)\n",
    "            res.append(len(arr))                            \n",
    "            arr = (arr[:k][::-1]+arr[k:])[::-1][:-1]\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        # 每次找到最大的元素 经过两次翻转放到队尾\n",
    "\n",
    "        ans = []\n",
    "        for n in range(len(arr), 1, -1):\n",
    "            index = 0\n",
    "            for i in range(n):\n",
    "                if arr[i] > arr[index]:\n",
    "                    index = i\n",
    "\n",
    "            if index == n - 1:\n",
    "                continue\n",
    "\n",
    "            m = index\n",
    "\n",
    "            arr[:m+1] = reversed(arr[:m+1])\n",
    "            arr[:n] = reversed(arr[:n])\n",
    "\n",
    "            ans.append(index+1)\n",
    "            ans.append(n)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        j = len(arr)\n",
    "        a = []\n",
    "        t = 0\n",
    "        while j >= 1:\n",
    "            maxs = max(arr[0:j])\n",
    "            m = arr.index(maxs)\n",
    "            if m == 0:\n",
    "                t+=1\n",
    "                arr[0:j] = arr[j-1:-1:-1]\n",
    "                a.append(j)\n",
    "            if m > 0 and m < j-1 :\n",
    "                t+=1\n",
    "                arr[0:m+1] = arr[m:-1:-1]\n",
    "                a.append(m+1)\n",
    "                arr[0:j] = arr[j-1:-1:-1]\n",
    "                a.append(j)\n",
    "            j-=1\n",
    "        if t <= 10*len(arr):\n",
    "            return a'''\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            x = arr.index(len(arr))\n",
    "            res.append(x+1)\n",
    "            res.append(len(arr))\n",
    "            arr = (arr[:x+1][::-1]+arr[x+1:])[::-1][:-1]\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = sorted(arr)\n",
    "        ans = []\n",
    "        if res == arr:\n",
    "            return ans\n",
    "        res = res[::-1]\n",
    "        length = len(res)\n",
    "        for i in range(length):\n",
    "            index = arr.index(res[i])\n",
    "            ans.append(index+1) #把最大值翻转到第一位\n",
    "            arr[:index+1] = arr[:index+1][::-1]\n",
    "            ans.append(len(arr)-i) #把最大值翻转到最后\n",
    "            arr[:length-i] = arr[:length-i][::-1]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = []\n",
    "        for i in range(n, 0, -1):\n",
    "            if i not in arr[0:i]:\n",
    "                continue\n",
    "            largest_id = arr[0:i].index(i)\n",
    "            arr[:largest_id+1] = arr[largest_id::-1]\n",
    "            res.append(largest_id + 1)\n",
    "            arr[:i] = arr[i-1::-1]\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(arr)\n",
    "        for i in range(n - 1,0,-1):\n",
    "            if arr[i] == i + 1:\n",
    "                continue\n",
    "            j = arr.index(i + 1)\n",
    "            if j:\n",
    "                ans.append(j + 1)\n",
    "                arr[:j + 1] = arr[:j + 1][::-1]\n",
    "            ans.append(i + 1)\n",
    "            arr[:i + 1] = arr[:i + 1][::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for n in range(len(arr), 1, -1):\n",
    "            idx = 0\n",
    "            for i in range(n):\n",
    "                if arr[i] > arr[idx]:\n",
    "                    idx = i\n",
    "            if idx == n - 1:\n",
    "                continue\n",
    "            left, right = 0, idx\n",
    "            while left < right:\n",
    "                arr[left], arr[right] = arr[right], arr[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                arr[left], arr[right] = arr[right], arr[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            res.append(idx + 1)\n",
    "            res.append(n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            _, idx = max((arr[j], j) for j in range(n - i))\n",
    "            arr[:idx+1] = arr[idx::-1]\n",
    "            arr[:n-i] = arr[n-i-1::-1]\n",
    "            res.append(idx + 1)\n",
    "            res.append(n - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        j = len(arr)\n",
    "        a = []\n",
    "        t = 0\n",
    "        while j >= 1:\n",
    "            maxs = max(arr[0:j])\n",
    "            m = arr.index(maxs)\n",
    "            if m == 0:\n",
    "                t+=1\n",
    "                arr[0:j] = arr[j-1:-1:-1]\n",
    "                a.append(j)\n",
    "            if m > 0 and m < j-1 :\n",
    "                t+=1\n",
    "                arr[0:m+1] = arr[m:-1:-1]\n",
    "                a.append(m+1)\n",
    "                arr[0:j] = arr[j-1:-1:-1]\n",
    "                a.append(j)\n",
    "            j-=1\n",
    "        if t <= 10*len(arr):\n",
    "            return a'''\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            x = arr.index(len(arr))\n",
    "            if x!=len(arr)-1:\n",
    "                res.append(x+1)\n",
    "                res.append(len(arr))\n",
    "            arr = (arr[:x+1][::-1]+arr[x+1:])[::-1][:-1]\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = []\n",
    "        for x in range(n, 0, -1):\n",
    "            i = arr.index(x)\n",
    "            res.extend((i+1, x))\n",
    "            arr = arr[:i:-1] + arr[:i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(arr)\n",
    "        while n:\n",
    "            i = arr.index(n)\n",
    "            if i == n - 1:\n",
    "                n -= 1\n",
    "                continue\n",
    "            ans.append(i + 1)\n",
    "            arr = arr[:i + 1][::-1] + arr[i + 1:]\n",
    "            ans.append(n)\n",
    "            arr = arr[:n][::-1] + arr[n:]\n",
    "            n -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pancakeSort(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        n = len(A)\n",
    "        while n :\n",
    "            idx = A.index(n)\n",
    "            res.append(idx+1)\n",
    "            A = A[:idx+1][::-1]+A[idx+1:]\n",
    "            res.append(n)\n",
    "            A = A[:n][::-1]+A[n:]\n",
    "            n -= 1\n",
    "        # print(A)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        # 从大到小先将值放到对应位置\n",
    "        # 找到剩余最大值的的位置，从该位置进行反转，将最大位置放到最左边\n",
    "        # 然后再从已排好序的左侧进行反转，将剩余最大值放到正确位置\n",
    "        r = len(arr)\n",
    "        target = sorted(arr)\n",
    "        ans = []\n",
    "        while arr != target:\n",
    "            # print(f\"arr:{arr}, r:{r}\")\n",
    "            curMax = max(arr[:r])\n",
    "            curMaxIndex = arr.index(curMax)\n",
    "            if curMaxIndex + 1 == curMax: \n",
    "                # 当前最大值在正确位置, 不用操作\n",
    "                r = curMaxIndex\n",
    "            else:\n",
    "                # 以当前最大值索引为k转到最左侧\n",
    "                ans.append(curMaxIndex+1)\n",
    "                arr[:curMaxIndex+1] = arr[:curMaxIndex+1][::-1]\n",
    "                # 以右侧已排好序位置左侧开始翻转，将剩余左侧最大值翻转到右侧\n",
    "                ans.append(r)\n",
    "                arr[:r] = arr[:r][::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        end = len(arr)\n",
    "        res = []\n",
    "        while end > 1:\n",
    "            max_num = max(arr[:end])\n",
    "            max_ind = arr.index(max_num)\n",
    "            if max_ind != 0:\n",
    "                res.append(max_ind+1)\n",
    "                arr[:max_ind+1] = arr[:max_ind+1][::-1]\n",
    "            res.append(end)\n",
    "            arr[:end] = arr[:end][::-1]\n",
    "            end -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for n in range(len(arr), 1, -1):\n",
    "            index = 0\n",
    "            for i in range(n):\n",
    "                if arr[i] > arr[index]:\n",
    "                    index = i\n",
    "            if index == n - 1:\n",
    "                continue\n",
    "            m = index\n",
    "            for i in range((m + 1) // 2):\n",
    "                arr[i], arr[m - i] = arr[m - i], arr[i]\n",
    "            for i in range(n // 2):\n",
    "                arr[i], arr[n - 1 - i] = arr[n - 1 - i], arr[i]\n",
    "            ans.append(index + 1)\n",
    "            ans.append(n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans, n = [], len(arr)\n",
    "        for val in range(1, n + 1):\n",
    "            for i in range(n):\n",
    "                if arr[i] == val: break\n",
    "            if i > 0: ans.append(i)\n",
    "            ans.append(i + 1)\n",
    "            del arr[i]\n",
    "            arr.insert(0, val)\n",
    "        ans.append(n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        # 1 2 4 5 3\n",
    "        # 2 1 4 5 3\n",
    "        # 5 4 1 2 3\n",
    "        # 3 2 1 4 5\n",
    "        # 1 2 3 4 5\n",
    "        ans=[]\n",
    "        buff=[arr[0]]\n",
    "        n=len(arr)\n",
    "        for i in range(1,n):\n",
    "            num=arr[i]\n",
    "            idx=bisect(buff,num)\n",
    "            if idx==i:\n",
    "                pass\n",
    "            elif idx==0:\n",
    "                ans.extend([i-1,i])\n",
    "            else:\n",
    "                ans.extend([idx-1,i-1,i,idx])\n",
    "            buff.insert(idx,num)\n",
    "            #print('#',buff)\n",
    "        #print(ans)\n",
    "        ans=[a+1 for a in ans if a>0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(arr)\n",
    "        for _ in range(n):\n",
    "            #print(arr)\n",
    "            max_value = max(arr)\n",
    "            pos = arr.index(max_value)\n",
    "            if pos == 0:\n",
    "                arr = arr[::-1]\n",
    "                res = res + [len(arr)]\n",
    "            elif pos == len(arr)-1:\n",
    "                arr = arr[:-1]\n",
    "                continue\n",
    "            else:\n",
    "                res = res + [pos+1,len(arr)]\n",
    "                arr = arr[0:pos+1][::-1]+arr[pos+1:]\n",
    "                print(arr)\n",
    "                arr = arr[::-1]\n",
    "            arr = arr[:-1]\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        j = len(arr) - 1 ## [0:j] 代表需要排序的数组, 换言之, j后面的数据都已排序完成\n",
    "        ans = []\n",
    "        \n",
    "        def reverse(i, j):\n",
    "            while i<j:\n",
    "                tmp = arr[i]\n",
    "                arr[i] = arr[j]\n",
    "                arr[j] = tmp\n",
    "                i+=1\n",
    "                j-=1\n",
    "        \n",
    "        while j >= 0:\n",
    "            maxNum, maxIndex = arr[0], 0\n",
    "            for i in range(1, j+1):\n",
    "                if arr[i] > maxNum:\n",
    "                    maxNum = arr[i]\n",
    "                    maxIndex = i\n",
    "            if maxIndex != j:\n",
    "                reverse(0, maxIndex)\n",
    "                ans.append(maxIndex + 1)\n",
    "                reverse(0, j)\n",
    "                ans.append(j + 1)\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        # 翻成逆序，再翻一下就是正序\n",
    "        n = len(arr)\n",
    "        if n<=1:\n",
    "            return []\n",
    "\n",
    "        # 把最大的翻到最后\n",
    "        \n",
    "        max_val=0\n",
    "        max_loc=0\n",
    "        for i, val in enumerate(arr):\n",
    "            if val>max_val:\n",
    "                max_val=val\n",
    "                max_loc=i+1\n",
    "        \n",
    "        # 操作列表\n",
    "        opt = []\n",
    "        if max_loc < n:\n",
    "            opt.append(max_loc)\n",
    "            arr[0:max_loc] = arr[max_loc-1::-1]\n",
    "            if arr[-1]!=max_val:\n",
    "                opt.append(n)\n",
    "                arr.reverse()\n",
    "\n",
    "        opt.extend(self.pancakeSort(arr[:-1]))\n",
    "\n",
    "        return opt\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 3241\n",
    "# 4231 3\n",
    "# 1324 4\n",
    "# 2314 3\n",
    "# 3214 2\n",
    "# 1234 3\n",
    "        \n",
    "# 3241\n",
    "\n",
    "# 4231\n",
    "# 1324\n",
    "# 3124\n",
    "# 2134\n",
    "# 1234"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(arr)\n",
    "        while n:\n",
    "            idx = arr.index(n)\n",
    "            res.append(idx+1)\n",
    "            arr = arr[:idx+1][::-1]+arr[idx+1:]\n",
    "            res.append(n)\n",
    "            arr = arr[:n][::-1] +arr[n:]\n",
    "            n -=1\n",
    "        return res\n",
    "        # def q(idx):\n",
    "        #     start = 0\n",
    "        #     while start < idx:\n",
    "        #         arr[start], arr[idx] = arr[idx], arr[start]\n",
    "        #         start +=1\n",
    "        #         idx -=1\n",
    "\n",
    "        # for i in range(n,0,-1):\n",
    "        #     max_idx = arr.index(max(arr))\n",
    "        #     if max_idx == i-1:\n",
    "        #         continue\n",
    "        #     if max_idx !=0:\n",
    "        #         q(max_idx)\n",
    "        #         res.append(max_idx+1)\n",
    "        #     q(max_idx-1)\n",
    "        #     res.append(max_idx)\n",
    "        # return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        def sortMax(arr):\n",
    "            n = len(arr)\n",
    "            k  = arr.index(n) + 1\n",
    "            #coppy = deepcopy(arr)\n",
    "\n",
    "            arr = arr[k-1::-1] + arr[k:]\n",
    "            arr = arr[::-1]\n",
    "            return arr,[k,n]\n",
    "        \n",
    "        while arr :\n",
    "            res += sortMax(arr)[1]\n",
    "            arr = sortMax(arr)[0][:-1]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        def flip(arr, k):\n",
    "            arr[:k] = reversed(arr[:k])\n",
    "        \n",
    "        res = []\n",
    "        n = len(arr)\n",
    "\n",
    "        for value in range(n, 0, -1):\n",
    "            index = arr.index(value)\n",
    "            if index != value - 1:\n",
    "                if index != 0:\n",
    "                    res.append(index + 1)\n",
    "                    flip(arr, index + 1)\n",
    "                res.append(value)\n",
    "                flip(arr, value)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr) \n",
    "        def swaparr(a, b):\n",
    "            while a < b:\n",
    "                arr[a], arr[b] = arr[b], arr[a] \n",
    "                a += 1\n",
    "                b -= 1 \n",
    "        ans = [] \n",
    "        for r in range(n-1, -1, -1):\n",
    "            j = 0 \n",
    "            for i in range(r+1):\n",
    "                if arr[j] < arr[i]:\n",
    "                    j = i \n",
    "            #print(r, j)\n",
    "            if j == r:\n",
    "                continue \n",
    "            elif j == 0:\n",
    "                ans.append(r+1) \n",
    "                swaparr(0, r)\n",
    "            else:\n",
    "                ans.append(j+1) \n",
    "                swaparr(0, j)\n",
    "                ans.append(r+1) \n",
    "                swaparr(0, r)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n=len(arr)-1\n",
    "        while n>=0 and arr[n]==n+1:\n",
    "            n-=1\n",
    "        if n<0:\n",
    "            return []\n",
    "        res=n+1\n",
    "        ans=[]\n",
    "        while res>1:\n",
    "            l=0\n",
    "            r=0\n",
    "            while arr[r]!=res:\n",
    "                r+=1\n",
    "            ans.append(r+1)\n",
    "            while l<r:\n",
    "                arr[l],arr[r]=arr[r],arr[l]\n",
    "                l+=1\n",
    "                r-=1\n",
    "            l1=0\n",
    "            l2=res-1\n",
    "            ans.append(res)\n",
    "            while l1<l2:\n",
    "                arr[l1],arr[l2]=arr[l2],arr[l1]\n",
    "                l1+=1\n",
    "                l2-=1\n",
    "            res-=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        # 将nums中target通过最多2次翻转,放在它正确的下标上, 返回[翻转次数]\n",
    "        def flip(nums, target):\n",
    "            nonlocal arr\n",
    "            flipCount = []\n",
    "            num_idx = {num: i for i, num in enumerate(nums)}\n",
    "            sortedNums = sorted(nums)\n",
    "            correctIndex = sortedNums.index(target)\n",
    "            curIndex = num_idx[target]\n",
    "            if curIndex == correctIndex:\n",
    "                return [0]\n",
    "\n",
    "            flipCount.append(num_idx[target] + 1)\n",
    "            nums = nums[:curIndex+1][::-1] + nums[curIndex+1:]\n",
    "            flipCount.append(correctIndex + 1)\n",
    "            nums = nums[:correctIndex+1][::-1] + nums[correctIndex+1:]\n",
    "            arr = nums[::]\n",
    "            return flipCount\n",
    "\n",
    "        nums = sorted(arr, reverse=True)\n",
    "        ans = []\n",
    "        for num in nums:\n",
    "            curFlip = flip(arr, num)\n",
    "            if curFlip != [0]:\n",
    "                ans += curFlip\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ls=sorted(arr)\n",
    "        n=len(arr)\n",
    "        ret=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if ls[i]==arr[i]:\n",
    "                continue\n",
    "            j=arr.index(ls[i])\n",
    "            ret.append(j+1)\n",
    "            ret.append(i+1)\n",
    "            tp1=arr[:j]\n",
    "            tp2=arr[j+1:i+1]\n",
    "            arr=tp2[::-1]+tp1+ls[i:]\n",
    "            #print(arr)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\r\n",
    "        if len(arr)<=1:\r\n",
    "            return [1,len(arr)]\r\n",
    "        n=len(arr)\r\n",
    "        idx=arr.index(n)+1\r\n",
    "        return [idx,n]+self.pancakeSort((arr[:idx][::-1]+arr[idx:])[::-1][:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        end = len(arr)\n",
    "        res = []\n",
    "        while end > 1:\n",
    "            max_num = max(arr[:end])\n",
    "            max_ind = arr.index(max_num)\n",
    "            if max_ind != 0:\n",
    "                res.append(max_ind+1)\n",
    "                arr[:max_ind+1] = arr[:max_ind+1][::-1]\n",
    "            res.append(end)\n",
    "            arr[:end] = arr[:end][::-1]\n",
    "            end -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        # 1 2 4 5 3\n",
    "        # 2 1 4 5 3\n",
    "        # 5 4 1 2 3\n",
    "        # 3 2 1 4 5\n",
    "        # 1 2 3 4 5\n",
    "        ans=[]\n",
    "        buff=[arr[0]]\n",
    "        n=len(arr)\n",
    "        for i in range(1,n):\n",
    "            num=arr[i]\n",
    "            idx=bisect(buff,num)\n",
    "            if idx==i:\n",
    "                pass\n",
    "            elif idx==0:\n",
    "                ans.extend([i-1,i])\n",
    "            else:\n",
    "                ans.extend([idx-1,i-1,i,idx])\n",
    "            buff.insert(idx,num)\n",
    "        ans=[a+1 for a in ans if a>0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        N = len(arr)\n",
    "        res = []\n",
    "        for x in range(N, 0, -1):\n",
    "            i = arr.index(x)\n",
    "            res.extend([i + 1, x])\n",
    "            arr = arr[:i:-1] + arr[:i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for n in range(len(arr), 1, -1):\n",
    "            index = 0\n",
    "            for i in range(n):\n",
    "                if arr[i] > arr[index]:\n",
    "                    index = i\n",
    "            if index == n - 1:\n",
    "                continue\n",
    "            m = index\n",
    "            for i in range((m + 1) // 2):\n",
    "                arr[i], arr[m - i] = arr[m - i], arr[i]  # 原地反转\n",
    "            for i in range(n // 2):\n",
    "                arr[i], arr[n - 1 - i] = arr[n - 1 - i], arr[i]  # 原地反转\n",
    "            ans.append(index + 1)\n",
    "            ans.append(n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for cur in range(len(arr), 0, -1):\n",
    "            i = arr.index(cur) + 1\n",
    "            arr[:i] = arr[:i][::-1]\n",
    "            arr[:cur] = arr[:cur][::-1]\n",
    "            ans.extend((i, cur))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\r\n",
    "        if len(arr)<=1:\r\n",
    "            return [1,len(arr)]\r\n",
    "        n=len(arr)\r\n",
    "        idx=arr.index(n)+1\r\n",
    "        return [idx,n]+self.pancakeSort((arr[:idx][::-1]+arr[idx:])[::-1][:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        # 设有n个煎饼，将最大的煎饼翻转到arr的最后，再对前n-1个煎饼进行相同的翻转操作。（缩小问题规模）\n",
    "        # 每次将最大的煎饼翻转到最后，需要两步翻转;\n",
    "        # 找到最大值的索引idx，并将idx之前的煎饼翻转;\n",
    "        # 将arr整体翻转；（除了最后已经翻转完的煎饼）\n",
    "        if not arr:\n",
    "            return []\n",
    "        res = []\n",
    "        idx = arr.index(max(arr)) #最大的饼idx\n",
    "\n",
    "        arr = arr[:idx+1][::-1] + arr[idx+1:]\n",
    "        arr = arr[::-1]\n",
    "        res += [idx+1, len(arr)]\n",
    "        temp = self.pancakeSort(arr[:-1]) \n",
    "        res = res + temp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for x in sorted(arr, reverse=True):\n",
    "            idx = arr.index(x) + 1\n",
    "            if idx < len(arr):\n",
    "                ans.append(idx)\n",
    "                ans.append(len(arr))\n",
    "                arr = arr[idx:][::-1] + arr[:idx]\n",
    "            arr.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        def backtrack(arr, n):\n",
    "            if n==1:return\n",
    "            max_cake = max(arr[:n])\n",
    "            max_index = arr.index(max_cake)\n",
    "            self.reverseArr(arr, 0, max_index)\n",
    "            res.append(max_index+1)\n",
    "            self.reverseArr(arr, 0, n-1)\n",
    "            res.append(n)\n",
    "\n",
    "            backtrack(arr, n-1)\n",
    "        backtrack(arr, len(arr))\n",
    "        return res\n",
    "    \n",
    "    def reverseArr(self,arr, i, j):\n",
    "        while i<j:\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "            i+=1\n",
    "            j-=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for n in range(len(arr), 1, -1):\n",
    "            index = 0\n",
    "            for i in range(1, n):\n",
    "                if arr[i] > arr[index]:\n",
    "                    index = i\n",
    "            if index == n - 1:  # 如果最大值就是在最后一个位置\n",
    "                continue\n",
    "\n",
    "            m = index\n",
    "\n",
    "            for j in range((m + 1) // 2):   # index是从0开始的，所以需要加1\n",
    "                arr[j], arr[m - j] = arr[m - j], arr[j]\n",
    "            for k in range(n // 2):\n",
    "                arr[k], arr[n - k - 1] = arr[n - k - 1], arr[k]\n",
    "            ans.append(m + 1)\n",
    "            ans.append(n)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\r\n",
    "        if len(arr)<=1:\r\n",
    "            return [1,len(arr)]\r\n",
    "        return [arr.index(len(arr))+1,len(arr)]+self.pancakeSort((arr[:arr.index(len(arr))+1][::-1]+arr[arr.index(len(arr))+1:])[::-1][:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        self.dp(arr)\n",
    "        return self.res\n",
    "    def dp(self, arr):\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return\n",
    "        index = arr.index(max(arr))\n",
    "        if index != n - 1:\n",
    "            arr = self.swap(arr, index + 1)\n",
    "            arr = self.swap(arr, n)\n",
    "        self.pancakeSort(arr[:-1])\n",
    "\n",
    "    def swap(self, arr, k):\n",
    "        self.res.append(k)\n",
    "        l, r = 0, k - 1\n",
    "        while l < r:\n",
    "            arr[l], arr[r] = arr[r], arr[l]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            max_num = max(arr)\n",
    "            idx = arr.index(max_num)\n",
    "            k = idx+1\n",
    "            res.append(k)\n",
    "            res.append(len(arr))                            \n",
    "            arr = (arr[:k][::-1]+arr[k:])[::-1][:-1]\n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        def reverse(i,j):\n",
    "            while(i<j):\n",
    "                arr[i],arr[j] = arr[j],arr[i]\n",
    "                i+=1\n",
    "                j-=1\n",
    "\n",
    "        def myPancakeSort(end):\n",
    "            if end==0:\n",
    "                return\n",
    "            max_index = 0\n",
    "            max_arr = arr[0]\n",
    "            for i in range(end+1):\n",
    "                if arr[i]>max_arr:\n",
    "                    max_arr=arr[i]\n",
    "                    max_index=i\n",
    "            result.append(max_index+1)\n",
    "            reverse(0,max_index)\n",
    "            # arr[:max_index+1] = arr[max_index:-len(arr)-1:-1]\n",
    "            result.append(end+1)\n",
    "            reverse(0,end)\n",
    "            # arr[:end+1] = arr[end:-len(arr)-1:-1]\n",
    "            myPancakeSort(end-1)\n",
    "        \n",
    "        myPancakeSort(len(arr)-1)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = []\n",
    "        for i in range(n, 0, -1):\n",
    "            index = arr.index(i)\n",
    "            if index + 1 == i:\n",
    "                continue\n",
    "            if index != 0:\n",
    "                arr[:index+1] = reversed(arr[:index+1])\n",
    "                res.append(index + 1)\n",
    "            arr[:i] = reversed(arr[:i])\n",
    "            res.append(i)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        def reverse_k(arr):\n",
    "            return arr[::-1]\n",
    "\n",
    "        if len(arr) == 1:\n",
    "            return []\n",
    "        reverse_idx = []\n",
    "        max_idx = 0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] > arr[max_idx]:\n",
    "                max_idx = i \n",
    "        reverse_idx.append(max_idx+1)\n",
    "        arr = reverse_k(arr[:max_idx+1])+arr[max_idx+1:]\n",
    "        reverse_idx.append(len(arr))\n",
    "        arr = reverse_k(arr)\n",
    "        reverse_idx += self.pancakeSort(arr[:len(arr)-1])\n",
    "        return reverse_idx\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        return (([idx + 1, len(arr)] if idx else [len(arr)]) + self.pancakeSort(arr[idx+1:][::-1] + arr[:idx]) if (idx := arr.index(len(arr))) < len(arr) - 1 else self.pancakeSort(arr[:idx])) if arr else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def pancakeDo(self, arr, end):\r\n",
    "        left,right = 0,end\r\n",
    "        while left<right:\r\n",
    "            arr[left],arr[right] = arr[right],arr[left]\r\n",
    "            left += 1\r\n",
    "            right -= 1\r\n",
    "\r\n",
    "    def pancakeSortFun(self, arr, end, rst_list):\r\n",
    "        if end<=1:\r\n",
    "            return\r\n",
    "        index = arr.index(max(arr[:end]))\r\n",
    "        rst_list.append(index+1)\r\n",
    "        self.pancakeDo(arr,index)\r\n",
    "        print(arr)\r\n",
    "        rst_list.append(end)\r\n",
    "        self.pancakeDo(arr,end-1)\r\n",
    "        print(arr)\r\n",
    "        self.pancakeSortFun(arr,end-1,rst_list)\r\n",
    "\r\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\r\n",
    "        rst_list = list()\r\n",
    "        self.pancakeSortFun(arr,len(arr),rst_list)\r\n",
    "        return rst_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pancakeSort(self, arr: List[int]) -> List[int]:\n",
    "        if not arr:\n",
    "            return []\n",
    "        res = []\n",
    "        idx = arr.index(max(arr)) #最大的饼idx\n",
    "\n",
    "        arr = arr[:idx+1][::-1] + arr[idx+1:]\n",
    "        arr = arr[::-1]\n",
    "        res += [idx+1, len(arr)]\n",
    "        temp = self.pancakeSort(arr[:-1])\n",
    "        res = res + temp\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
